package cn.hdu.liang.ch2;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {2, 5, 7, 8, 9, 1, 2, 3, 4, 5};
        int[] temp = new int[10];
        int p = 0;
        int r = 9;
        mergeSort(a, p, r, temp);
        System.out.println(Arrays.toString(temp));
    }

    public static void mergeSort(int[] a, int p, int r, int[] t) {
        if(p < r) {
            int q = (p + r) / 2;
            mergeSort(a, p, q, t);
            mergeSort(a, q + 1, r, t);
            merge(a, p, q, r, t);

        }
    }

    public static void merge(int[] a, int p, int q, int r, int[] t) {
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] L = new int[10];
        int[] R = new int[10];
        System.arraycopy(a, p, L, 0, n1);
        System.arraycopy(a, q + 1, R, 0, n2);
        L[n1] = 100;
        R[n2] = 100;

        int i = 0, j = 0, k = 0;

        while(L[i] != 100 && R[j] != 100) {
            if(L[i] <= R[j]) {
                t[k] = L[i];
                i++;
            } else {
                t[k] = R[j];
                j++;
            }
            k++;
        }

        if(i < j) {
            System.arraycopy(L, i, t, k, t.length - k);
        } else {
            System.arraycopy(R, j, t, k, t.length - k);
        }
    }

}
